#
# @lc app=leetcode.cn id=279 lang=python
#
# [279] 完全平方数
#

# @lc code=start
import math
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            max_eage = int(math.sqrt(i))
            for j in range(1, max_eage+1):
                dp[i] = min(dp[i-j**2]+1, dp[i])
        if dp[-1] == float('inf'):
            return -1
        else:
            return dp[-1]
        
# @lc code=end

